package Sort;

import java.util.Arrays;

/**
 * @author Liangyaoyun
 */
public class HeapSort {

    public void heapSort(int[] nums) {
        int tmp;
        //1.从数组变成堆
        //无需代码
        //2.将堆调整成为大根堆
        for (int root = nums.length / 2 - 1; root >= 0; root--) {
            maxHeap(nums, root, nums.length - 1);
        }
        //3.将堆顶出堆，然后再将堆结构整体调整为大根堆，循环往复，直到堆当中只剩余1个元素为止
        //end变量表示的是当前堆结构对应的数组中，最后一位元素的下标
        for (int end = nums.length - 1; end > 0; end--) {
            //3.1将堆顶元素（nums[0]）和堆当中最后一个元素进行交换
            tmp = nums[0];
            nums[0] = nums[end];
            nums[end] = tmp;

            //3.2将以nums[0]为根的整个堆结构再次调整成为大根堆
            maxHeap(nums, 0, end - 1);
        }

    }

    /**
     * 将以数组中指定下标为根的子堆
     * 调整成为大根堆的方法
     */
    private void maxHeap(int[] nums, int root, int end) {

        int tmp;

        //1.根据给定的（子）堆顶元素在数组nums中的下标，找到两个孩子节点对应的数组下标
        int lChild = 2 * root + 1;
        int rChild = 2 * root + 2;

        //递归出口：如果当前堆顶元素是一个叶子节点，那么直接退出递归
        if (lChild > end) {
            return;
        }

        //2.找到两个孩子当中与父节点可能发生交换的一个
        int change = rChild <= end && nums[rChild] > nums[lChild] ? rChild : lChild;

        //3.1如果找到的孩子节点的取值大于父节点的取值，则将孩子与父节点进行交换
        if (nums[change] > nums[root]) {
            tmp = nums[root];
            nums[root] = nums[change];
            nums[change] = tmp;
            //3.2交换之后的子堆堆顶可能失去大根堆特性，递归调整
            maxHeap(nums, change, end);
        } else {
            //3.3较大的孩子也小于父节点的取值，不需要调整当前堆就是大根堆
            return;
        }

    }

    /*
    作业：通过循环的方式实现堆排序中的maxHeap方法（替代递归）
     */

    public static void main(String[] args) {

        int[] nums = new int[]{6, 1, 0, 3, 9, 8, 4, 7, 5, 2};
        HeapSort hs = new HeapSort();
        hs.heapSort(nums);
        System.out.println(Arrays.toString(nums));

    }

}
